<?php
/**
 * @title 336. 回文对 -
 * @author start2004
 */

ini_set("memory_limit", "512M");

class Solution {

    /**
     * @param String[] $words
     * @return Integer[][]
     */
    function palindromePairs($words) {
        /**
         * @since 2021-09-01 每个字符都不同
         */
        $hashWordArray = [];
        foreach ($words as $k => $word){
            $hashWordArray[$word] = $k;
        }
        // return $hashWordArray;

        /**
         * @since 2021-09-01 是否存在空字符串
         */
        if(isset($hashWordArray[""])){
            $emptykey = $hashWordArray[""];
            unset($words[$emptykey]);
        } else {
            $emptykey = false;
        }

        /**
         * @since 2021-08-31 结果集
         */
        $result = [];

        /**
         * @since 2021-08-31 回文对
         */
        foreach ($words as $k1 => $word){
            // echo "k={$k1}, word={$word}", PHP_EOL;

            /**
             * @since 2021-09-01 `word` + `*word`
             */
            $suffix = "";
            for($s=0, $len=strlen($word); $s<$len; $s++){
                $suffix = $word[$s] . $suffix;
                // echo "suffix={$suffix}";

                /**
                 * @since 2021-09-01 是否存在对应字符
                 */
                if(isset($hashWordArray[$suffix])){
                    $k2 = $hashWordArray[$suffix];
                    $k = "{$k1}_{$k2}";

                    /**
                     * @since 2021-09-01 不能是自己
                     * @since 2021-09-01 不能重复
                     * @since 2021-09-01 检查是否有回文
                     */
                    if(($k1 != $k2) AND !isset($result[$k]) AND self::isPalindrome($word, $s+1, $len-1)){
                        // echo ", find k={$k2}";
                        $result[$k] = [$k1, $k2];
                    } else {}
                } else {}
                // echo PHP_EOL;
            }

            /**
             * @since 2021-09-01 `word*` + `word`
             */
            $prefix = "";
            for($p=$len-1; $p>=0; $p--){
                $prefix = $prefix . $word[$p];

                /**
                 * @since 2021-09-01 是否存在对应字符
                 */
                if(isset($hashWordArray[$prefix])){
                    $k2 = $hashWordArray[$prefix];
                    $k = "{$k2}_{$k1}";

                    /**
                     * @since 2021-09-01 不能是自己
                     * @since 2021-09-01 不能重复
                     * @since 2021-09-01 检查是否有回文
                     */
                    if(($k1 != $k2) AND !isset($result[$k]) AND self::isPalindrome($word, 0, $p-1)){
                        $result[$k] = [$k2, $k1];
                    } else {}
                } else {}
            }

            /**
             * @since 2021-09-01 存在空字符串, 检查自己是否是回文
             */
            if($emptykey !== false AND self::isPalindrome($word, 0, $len-1)){
                $result[] = [$emptykey, $k1];
                $result[] = [$k1, $emptykey];
            } else {}
        }

        /**
         * @return
         */
        return array_values($result);
    }

    /**
     * @title 检查字符串是否回文
     * @author start2004
     * @since 2021-08-31 Created
     *
     * @param string $s
     * @param int $left
     * @param int $right
     * @return boolean
     */
    function isPalindrome($s = '', $left = 0, $right = 0){
        /**
         * @since 2021-08-31 逐位检查
         */
        // echo "s={$s}, left={$left}, right={$right}", PHP_EOL;
        while($left < $right){
            if($s[$left] != $s[$right]){
                return false;
                break;
            } else {}

            /**
             * @since 2021-08-31 下次
             */
            $left++;
            $right--;
        }

        /**
         * @return
         */
        return true;
    }
}

/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.06_4.php
 */
$datas = [
    ["","behaci","aicidh","cdfeicf","fedihch","hebhci","bccfga","fbgdd","f","bc"], // [[8,0],[0,8]]
    ["abcd","dcba","lls","s","sssll"], // [[0,1],[1,0],[3,2],[2,4]]
    // ["a",""],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    // var_dump($data);

    $obj = new Solution();
    $result = $obj->palindromePairs($data);
    if(count($result) <= 20){
        var_dump($result);
    } else {
        var_dump(count($result));
    }
    echo str_repeat("<br>", 3);
}
$xhprof->end();
